package com.cat.chapter054;
/**
 * @author cat
 * @description https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/
 * @create 2025/7/25 16:10
 * @since JDK17
 */

public class Solution02 {
    static int N = ((int) (1e5 + 10)), hmax, tmax, hmin, tmin;
    static int[] maxDeque = new int[N], minDeque = new int[N];
    static int[] arr;

    public int longestSubarray(int[] nums, int limit) {
        arr = nums;
        int ans = 0, n = arr.length;
        hmax = hmin = tmax = tmin = 0;
        for (int l = 0, r = 0; l < n; l++) {
            while (r < n && isOk(arr[r], limit)) {   // 如果可以加入则加入
                push(r++);
            }
            ans = Math.max(ans, r - l);
            pop(l);
        }
        return ans;
    }

    public boolean isOk(int num, int limit) {
        int max = hmax < tmax ? Math.max(arr[maxDeque[hmax]], num) : num;
        int min = hmin < tmin ? Math.min(arr[minDeque[hmin]], num) : num;
        return  max - min <= limit;
    }
    void push(int r) {
        while (hmax < tmax && arr[maxDeque[tmax - 1]] <= arr[r]) {  // 大 -> 小
            tmax--;
        }
        maxDeque[tmax++] = r;
        while (hmin < tmin && arr[minDeque[tmin - 1]] >= arr[r]) {    // 小 -> 大
            tmin--;
        }
        minDeque[tmin++] = r;
    }

    void pop(int l) {   // 条件写完整
        if (hmax < tmax && l == maxDeque[hmax]) hmax++;
        if (hmin < tmin && l == minDeque[hmin]) hmin++;
    }
}
